package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/
 * @create 2025/9/2 20:04
 * @since JDK17
 */

public class Solution55 {
    static int N = ((int) (1e9 + 7));
    public int maxProductPath(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        long[][][] dp = new long[n + 1][m + 1][2];
        dp[0][0][1] = dp[0][0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[0][i][0] = Math.max(dp[0][i - 1][0] * grid[0][i], dp[0][i - 1][1] * grid[0][i]);
            dp[0][i][1] = Math.min(dp[0][i - 1][0] * grid[0][i], dp[0][i - 1][1] * grid[0][i]);
        }
        for (int i = 1; i < n; i++) {
            dp[i][0][0] = Math.max(dp[i - 1][0][0] * grid[i][0], dp[i - 1][0][1] * grid[i][0]);
            dp[i][0][1] = Math.min(dp[i - 1][0][0] * grid[i][0], dp[i - 1][0][1] * grid[i][0]);
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                long a = dp[i][j - 1][0] * grid[i][j], b = dp[i][j - 1][1] * grid[i][j];
                long c = dp[i - 1][j][0] * grid[i][j], d = dp[i - 1][j][1] * grid[i][j];
                dp[i][j][0] = Math.max(Math.max(a, Math.max(b, c)), d);
                dp[i][j][1] = Math.min(Math.min(a, Math.min(b, c)), d);
            }
        }
        return dp[n - 1][m - 1][0] < 0 ? -1 : ((int) (dp[n - 1][m - 1][0] % N));
    }
}
